package alo.p4.work;

import java.util.Stack;

//给定一个栈，只使用push和pop逆置栈
public class StackReversal {
    public static void main(String[] args) {
        Stack<Integer> stack=new Stack<>();
        stack.push(0);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        for (Integer i : stack) {
            System.out.print(i);
        }//01234
        System.out.println();
        reverseStack(stack);
        for (Integer i : stack) {
            System.out.print(i);
        }//43210
    }
    //使用递归，效率并不高，时间复杂度O（n*n），空间复杂度O（n*n）
    //逆置从一个到n个，多次递归
    //递归出栈
    public static void reverseStack(Stack stack){
        if (stack.isEmpty()) return;
        int temp= (int) stack.pop();
        reverseStack(stack);
        insertAtBottom(stack,temp);
    }
    //返回后，进行逆置
    public static void insertAtBottom(Stack stack, int data){
        if (stack.isEmpty()){
            stack.push(data);
            return;
        }
        int temp= (int) stack.pop();
        insertAtBottom(stack,data);
        stack.push(temp);
    }
}
